package com.leetcodehot.problems;

public class problems142 {
    class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }

    /**
     * 环形链表推导公式：
     * 假设 从 head到入口的距离是a，从入口到相遇点的距离是b，从相遇点到入口的距离为c。
     * slow移动距离的两倍是fast的移动距离，当相遇时，slow一定环还没走完。
     * 那么就有  2*(a+b) = a + b + k(b+c) 假设 快指针多走了k圈。
     * 化简：
     * a-c = (k-1)*(b+c)
     * <p>
     * 我们现在想要找入口。假设从head触发。slow从相遇点出发。那么head走a步就能到达入口，
     * 而 a = (k-1)*(b+c) + c
     * 我们发现，假设slow从相遇点出发，走上a步，也就是走上(k-1)*(b+c) + c。
     * 相当于slow从相遇点走上了(k-1)圈后 再走上c 步。刚好也是到了入口的位置。
     * 所以 slow和head相遇的位置就是入口。
     */
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                //从下面开始走动
                while (slow != head) {
                    slow = slow.next;
                    head = head.next;
                }
                return head;
            }
        }
        return null;
    }
}
